\documentclass[12pt]{article}
%\usepackage{lingmacros}
%\usepackage{tree-dvips}
\usepackage[pdftex]{graphicx}
\usepackage{algorithm2e}

\begin{document}
\title{Homework 4 by Congle Zhang}
\maketitle


\section{Zero-Weight-Cycle Problem}
The key idea here is to prove Subset sum $\leq_q$ Zero-Weight-Cycle Problem. 

(1) \textbf{Claim 0: }Zero-Weight-Cycle Problem is in NP.

\textbf{Proof: }Given a cycle, we can check whether it is a cycle and check its weight by scanning it. So it is $O(n)$. 

(2)We now prove Subset sum $\leq_q$ Zero-Weight-Cycle Problem. Suppose the set has $N$ elements $S=\{w_1,w_2 \ldots w_N\}$. The subset sum is $W$. We can mapping this problem into zero-weight-cycle problem in following way: build directed graph $G=(V,E)$, where $V$ has $N+2$ nodes $V=\{s,t,n_1,n_2 \ldots n_N\}$. There are four kinds of edges: (a) For node $s$ and $n_i$, $e(s,n_i) = w_i$. (b) For node $n_i$ and $n_j$, edge $e(n_i,n_j) = w_j$. (c) For node $n_j$ and $t$, edge $e(n_j,t)=0$. (d) There is an edge $e(t,s)=-W$. 

\textbf{Claim 1: } The construction cost is polynomial.

\textbf{Proof: } There are at all $N+2$ nodes and $N^2+2N+1$ edges. So it is polynomial.

\textbf{Claim 2:} $S$ has a subset sum $W$ iff $G$ has a zero-weight-cycle.

\textbf{Proof: } $\Longrightarrow$ Suppose $\{w_{i_1}, w_{i_2}, \ldots w_{i_m}\}$ is a subset of $S$ sum $W$. Then there is a  cycle in $G$ as $(s,i_1),(i_1,i_2),(i_2,i_3)\ldots (i_m,t), (t,s)$. The sum weights in this cycle is $w_{i_1}+ w_{i_2}+ \ldots +w_{i_m}+0-W = 0$. True.

$\Longleftarrow$ Since the only edge in $G$ has negative weight is $(t,s)$, if there is an zero-weight-cycle, $(t,s)$ is in this cycle. It also can be noticed that $s$ has only out edges and $t$ only has in edges. So the cycle must be $(s,i_1),(i_1,i_2),(i_2,i_3)\ldots (i_m,t), (t,s)$. Since it is a zero weight cycle, we have $w_{i_1}+ w_{i_2}+ \ldots +w_{i_m}+0-W = 0$. Therefore $\{w_{i_1}, w_{i_2}, \ldots w_{i_m}\}$ is a subset of $S$ sum $W$. $\squre$

In sum, we have proved Subset sum $\leq_q$ Zero-Weight-Cycle Problem. Since Zero-Weight-Cycle Problem is in NP. We know it is NPC.

\section{Perfect Assembly Problem}
The key idea here is to prove Hamilton path $\leq_p$ perfect assembly problem.

(1) \textbf{Claim 0: }Perfect assembly problem  is in NP.

\textbf{Proof:} Given the sequence of $S_0=\{s_{i_1}, s_{i_2}, \ldots s_{i_n}\}$ and $T_0=\{t_{j_1}, t_{j_2}, \ldots t_{j_{n-1}}\}$. We can check whether $T_0$ is a perfect assembly by scanning $T_0$, so it is polynomial.

(2) We now prove Hamilton path $\leq_p$ perfect assembly problem. Given a directed graph $G=(V,E)$ with $N$ nodes and $M$ edges. Letting $\ell = \lceil \log_4 N \rceil$, we can encode $N$ nodes with $A,T,C,G$ in $\ell$ bits. For example, 100 is 1210 in quaternary system. Let $A=0,T=1,C=2,G=3$. We can write 100 as $TCTA$. Say $f(a)=x_a$ is the mapping function from an integer $a$ into a $\ell$ length string. Now, we can map node $v_i$ to $s_i$ by $s_i=f(i)f(i)$, where $f(i)f(i)$ is a $2\ell$ length string that its first half is equal to its second half. So the set $S$ has $N$ strings. We now map edges into $T$: if edge $(n_i,n_j)\in E$, we add string $t_{ij} = f(i)f(j)$ into $T$. Then there are $M$ elements in $T$. 

\textbf{Claim 1: } The construction cost is polynomial.

\textbf{Proof: } There are at all $N$ nodes and $M$ edge, $\ell = O(log N)$. So the construction is $O(log N(N+M))$, polynomial.

\textbf{Claim 2: } Each $t_{ij}$ is unique.

\textbf{Proof: } It comes from the fact that the code of each node is unique. 


\textbf{Claim 3: } $G$ has a hamilton path iff $S,T$ has the perfect assembly.

\textbf{Proof: }  $\Longrightarrow$ Let the hamilton path be $v_{i_1}, v_{i_2}, \ldots v_{i_n}$. There is a directed edge from $v_{i_k}$ to $v_{i_{k+1}}$, so $t_{i_k,i_{k+1}} \in T$.  Look at the permutation $s_{i_1}, s_{i_2}, \ldots s_{i_n}$ of $S$ and strings $t_{i_1,i_2}, t_{i_2,t_3}, \ldots t_{i_{n-1},t_n}$. It is not hard to see $T$ is the perfect assembly of $S$, since $t_{i_k,i_{k+1}}$ share its first $\ell$ bits with $s_{i_k}$'s last $\ell$ bits, and share its last $\ell$ bits with $s_{i_{k+1}}$'s first $\ell$ bits. 

$\Longleftarrow$ Suppose $s_{i_1}, s_{i_2}, \ldots s_{i_n}$ and $t_{j_1}, t_{j_2}, \ldots t_{j_{n-1}}$ is the perfect assembly. Thus $t_{j_k}$ is composed of the last $\ell$ bits of $s_{i_k}$ and the first $\ell$ bits of $s_{i_{k+1}}$. Since each $t \in T$ is unique, we know $t_{j_k}$ is $t_{i_k, i_{k+1}}$. Thus, there is a link from node $v_{i_k}$ to $v_{i_{k+1}}$. Therefore, $v_{i_1}, v_{i_2}, \ldots v_{i_n}$ compose a hamilton path.\\   

Together with above claims, we know Perfect assembly problem is NPC.

\section{Influence Maximization}
The key idea here is to prove Set Cover $\leq_p$ Influence Maximization.

(1) \textbf{Claim 0: } Influence Maximization is in NP.

\textbf{Proof: } The polynomial algorithm in P523 can find the set of adopters. 
 
(2) Now we show that Set Cover $\leq_p$ Influence Maximization. Given set $U$ of $n$ elements $a_1,a_2 \ldots a_n$, and subset $S_1,S_2,\ldots S_m$. We need to find at most $\ell$ subset to cover $U$. We build the directed bipartite graph $G=(V,E), V=X \cup Y$. For $X$ has $m$ nodes standing for $m$ subsets. $Y$ has $n$ nodes standing for $n$ elements of $U$. If $a_i \in S_j$, we add a directed edge $(x_j, y_i)$ in $G$. We set the node threshold for every $Y$ as $\frac{1}{n}$ (i.e. to guarantee whenever an $x$ is an adopter and $x$ link to $y$, $y$ is an adopter). Now we convert the set cover problem into a influence maximization problem with $k=\ell$ and $b=k+n$.

\textbf{Claim 1: } The construction cost is polynomial.

\textbf{Proof: } The graph has $n+m$ nodes and at most $nm$ edges. So the construction time is polynomial.

\textbf{Claim 2: }Set cover problem has a solution iff Influence Maximization on $G$ with $k=\ell$ and $b=\ell+n$.

\textbf{Proof: }  $\Longrightarrow$ suppose $S_1,S_2 \ldots S_\ell$ can cover $U$, we can choose $x_1,x_2, \ldots x_\ell$ as first. Since for any $y$, there exist $x_i$, $(x_i, y)$ is an  directed edge. We can see all $y$ will be adopters at last. Since for any $x_i$, there is no edge link to it. So in $X$ side, there are $\ell=k$ adopters at last. The total number of adopters is $\ell+n = b$.

 $\Longleftarrow$ When there is a solution for $G$ with $k=\ell$ and $b = \ell +n$. There are at most $n$ nodes being adopted in $Y$ side at last, so there are at least $k$ nodes (and at most $k$ of course) adopted in $X$ sides. Since nodes in $X$ side will not be influenced later, we get the fact that all these $k$ adopters are adopters at the very beginning. So there are no adopter in $Y$ side at the very beginning. Since finally there are $n$ adopters in $Y$ sides. we know for every $y$, there exist an adopted $x$ having a link $(x,y)$. Let the adopters in $X$ side be $x_1,x_2,\ldots x_k$, they correspond to $k$ subset $S_1,S_2,\ldots S_k$ cover $U$. 
 
 
Therefore, we proved that Set cover problem $\leq_p$ Influence Maximization problem. Since influence maximization is also in NP. It is NPC.
 
 
\section{Linear program}

(a) We introduce $z_1,z_2,z_3$ for 3 constrains. By setting $x_1=x_2=x_3 = 0$, we have $(0,0,0,6,2,0)$. Target function $F=0$. 

Increase $x_2$ by $0$ (change $x_2$, $z_3$ in basis), we have

\begin{eqnarray}
\begin{array}{ll}
max: x_1+7/3 x_3 - 2/3 z_3 &\\
z_1 = 6-3x_1 -16/3 x_3 + 2/3 z_3 &\geq 0\\
z_2 = 2-x_1-5/3 x_3 - x_2 + 1/3 z_3 &\geq 0\\
x_2 = 2/3 x_3 - 1/3 z_3 &\geq 0\\
x_1,x_3,z_3 &\geq 0
\end{array}
\end{eqnarray}


Increase $x_3$ by $9/8$ (change $x_3$, $z_1$ in basis), we have

\begin{eqnarray}
\begin{array}{ll}
max: 21/8 - 5/16 x_1 - 3/8 z_3 - 7/16 z_1 &\\
x_3 = 9/8 - 9/16 x_1 + 1/8 z_3 - 3/16 z_1 &\geq 0\\
x_2 = 3/4 - 3/8 x_1 + 1/12 z_3 - 1/8 z_1 - 1/3 z_3 &\geq 0\\
z_2 = 1/8 - 1/16 x_1 - x_2 + 1/8 z_3 + 5/16 z_1 &\geq 0\\
x_1,z_1,z_3 &\geq 0
\end{array}
\end{eqnarray}

We are done. The maximum value is $21/8$, 
\[
(x_1,x_2,x_3) = (0,3/4,9/8)
\]


(b) The dual problem is:
\begin{eqnarray}
\begin{array}{ll}
min: 6x_1+ x_2 &\\
3x_1+x_2 &\geq 1\\
2x_1+x_2+3x_3 &\geq 2\\
4x_1+x_2-2x_3 &\geq 1\\
x_1,x_2,x_3 & \geq 0
\end{array}
\end{eqnarray}

(c) Convert the problem into:

\begin{eqnarray}
\begin{array}{ll}
min: 6x_1+ x_2 &\\
3x_1+x_2 -z_1 &\geq 1\\
2x_1+x_2+3x_3 -z_2 &\geq 2\\
4x_1+x_2-2x_3 -z_3 &\geq 1\\
x_1,x_2,x_3 z_1,z_2,z_3& \geq 0
\end{array}
\end{eqnarray}

Start from corner point $(0,2,0,1,0,1)$, $(x_1,x_3,z_2)$ are basis, we have 

\begin{eqnarray}
\begin{array}{ll}
min: 4+2z_2 + 2x_1 - 6x_3 &\\
x_2=2+x_2-2x_1-3x_3 &\geq 0\\
z_1 = z_2 + x_1 -3x_3 +1 &\geq 0\\
z_3 = 1+z_2 + 2x_1-5x_3 &\geq 0\\
x_1,x_3,z_2 &\geq 0
\end{array}
\end{eqnarray}

Increase $x_3$ by $1/5$ (change $x_3$ and $z_3$ in basis), we have 

\begin{eqnarray}
\begin{array}{ll}
min: 14/5 + 4/5 z_2 - 2/5 x_1 + 1/5 z_3 &\\
x_3=1/5 + 1/5 z_2 + 2/5 x_1 -1/5 z_3 &\geq 0\\
z_1 = 2/5 + 8/5 z_2 - 1/5 x_1-3/5 z_3 &\geq 0\\
x_2 = 7/5+ 2/5 z_2 -16/5 x_1 -3/5 z_3 &\geq 0\\
x_1,x_3,z_2 &\geq 0
\end{array}
\end{eqnarray}

Increase $x_1$ by $7/16$ (change $x_1$ and $x_2$ in basis), we have

\begin{eqnarray}
\begin{array}{ll}
min: 21/8 + 3/4 z_2 + 1/8 x_2 + 1/5 z_3&\\
x_1 = 7/16 + 1/8 z_2 - 5/16 x_2 &\geq 0\\
x_3 = 1/5 +7/40 + \ldots & \geq 0\\
\ldots
\end{array}
\end{eqnarray}

We are done. The minimal value is 21/8 by taking 

\[(x_1,x_2,x_3) = (7/16,0,3/8)\]
\end{document}
